347 前 K 个高频元素

https://leetcode.cn/leetbook/read/top-interview-questions-medium/xvzpxi/

cost:

class Node {
public:
    int fre;
    int val;
};

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> frequencies;
        vector<Node> heap(k + 1);
        for (const int& num : nums) {
            frequencies[num] += 1;
        }
        for (const auto [num, fre] : frequencies) {
            if (fre <= heap[1].fre) {
                continue;
            }
            heap[1] = Node{fre : frequencies[num], val : num};
            this->reorderHeap(heap, 1);
        }
        vector<int> res;
        for (int i = 1; i < heap.size(); i++) {
            res.push_back(heap[i].val);
        }
        return res;
    }

private:
    void reorderHeap(vector<Node>& heap, int i) {
        if (i >= heap.size()) {
            return;
        }
        if (i * 2 < heap.size() && heap[i].fre > heap[i * 2].fre) {
            std::swap(heap[i], heap[i * 2]);
            this->reorderHeap(heap, i * 2);
        }
        if (i * 2 + 1 < heap.size() && heap[i].fre > heap[i * 2 + 1].fre) {
            std::swap(heap[i], heap[i * 2 + 1]);
            this->reorderHeap(heap, i * 2 + 1);
        }
    }
};